package leetcode.weekly.week318;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

//Solution4Test
public class Solution4 {

//	public long minimumTotalDistance(List<Integer> robot, int[][] factory) {
//		Collections.sort(robot);
//		Arrays.sort(factory, (a, b) -> a[0] - b[0]);
//		long ans = 0;
//		return ans;
//	}
	
	// https://leetcode.cn/u/v7fgg/  抱抱的，写的真好看啊，还好懂。
	public long minimumTotalDistance1(List<Integer> robot, int[][] factory) {
		Collections.sort(robot);
		Arrays.sort(factory, (a, b) -> a[0] - b[0]);
		int m = robot.size();
		int n = factory.length;
		long ans[][] = new long[m + 1][n + 1];
		for (int i = 0; i <= m; i++) {
			Arrays.fill(ans[i], (long) 1e18);
		}
		ans[0][0] = 0;
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				ans[0][j] = 0L;
				ans[i][j] = ans[i][j - 1];
				long sum = 0;
				for (int k = 1; k <= factory[j - 1][1] && k <= i; k++) {
					sum += Math.abs(robot.get(i - k) - factory[j - 1][0]);
					ans[i][j] = Math.min(ans[i][j], ans[i - k][j - 1] + sum);
				}
			}
		}
		return ans[m][n];
	}

}
